Computer based raster display systems generally utilize a frame buffer to store information describing the displayed image. The frame buffer contains information for each pixel location on the display screen. In order to reduce cost, the amount of information for each pixel is limited to, for example, eight bits. These bits are then generally used to specify one of a range of colors contained in a color palette. These colors are generally specified in an RGB (red, green, and blue) color format.
This display system architecture is very common in low cost personal computers. This works well when the user is selecting the color for each object, such as when generating a diagram. However, this type of system has not generally been well suited to the display of natural images from, for example, a color television camera.
Images from a color television camera, TV tuner, or video tape recorder are generally represented in a composite video format. This format describes each pixel color using a luminance value (typically called Y) and two chrominance values (typically called U and V). To display this image on a computer display screen of the design discussed above, the luminance and chrominance information must be converted to index values which select from one of the possible colors provided by the color palette.
There are numerous problems that must be solved when converting from YUV color space to RGB color space including the complexity of the color space transformation, the selection of the optimum color from the palette, and the banding that results from the limited range of colors available.
Algorithms for converting from YUV color space to RGB color space are well known in the art, but are computationally expensive, typically requiring a number of multiplication operations for each pixel. This presents a serious problem for video processing since high performance is required to achieve smooth motion. The computational overhead necessary for performing these calculations can prevent a system that must perform such a conversion from operating in real-time.
The number of colors available in the color palette will typically be considerably less than the number of colors that can be represented by the YUV color values. For example, a typical personal computer has a color palette with 256 colors. The YUV color data, on the other hand, may specify one of millions of colors. To display the YUV image on a personal computer, the number of colors must be dramatically reduced.
One of the steps to reducing the number of colors is to quantize the color components so that they are described with fewer bits. A side effect of this quantization is a visual artifact known in the art as banding. This is best understood by considering a gradual transition from one color to another. If this transition is made with enough steps, this transition will appear smooth, with no obvious discontinuities. However, as the information storing color information is reduced to a representation having fewer bits known as quantizing, the number of available intermediate colors is reduced, thus, decreasing the number of steps that can be utilized. The difference from one step to the next becomes exaggerated. The steps begin to appear as bands on the display and are particularly distracting in natural images.
A well known technique to reduce the effects of quantization is to add noise to the signal before quantizing. This technique is also known as dithering. This tends to make the transition from one step to the next less uniform and therefore less apparent to a viewer.
This approach to dithering has not typically been applied to image quantization. In certain experimental systems, noise has been added to the RGB components before quantization. However, when enough noise is added to reduce the banding effect, the resulting color values often have significantly different spectral content and the resulting image has unacceptable color speckling.
Once the pixel value has been converted to RGB space, algorithms are known for selecting the closest color from a color palette. However, these algorithms do not take advantage of our knowledge of the human vision system. Early color television research indicated a much higher sensitivity to intensity accuracy than to color accuracy. Nevertheless, conventional algorithms use only a simple error calculation in RGB space to determine the selected color rather than intensity.
Thus, several objects of this invention are to provide a fast, efficient method to convert color values specified in a luminance/chrominance format to values that can be stored in the frame buffer which will select an optimal color from the color palette, and to provide techniques to reduce the banding artifacts that often result from the use of a limited range of colors.